//重排链表
//https://leetcode.cn/problems/reorder-list/description/
public class Test {
    public static void main(String[] args) {
        //
    }
}

//Definition for singly-linked list.
class ListNode {
     int val;
     ListNode next;
     ListNode() {}
     ListNode(int val) { this.val = val; }
     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

class Solution {
    public void reorderList(ListNode head) {
        //0.特殊情况处理
        //只有一个节点
        if(head.next == null){
            return;
        }
        //只有两个节点
        if(head.next.next == null){
            ListNode temp = head.next;
            temp.next = head;
            head = temp;
        }

        //1.找到链表的中间节点（快慢指针）（拓展：找到链表的任意倒数个结点）
        ListNode slow = head;
        ListNode fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        if(fast.next!=null) slow = slow.next;
        //没用到ListNode temp = slow.next;//——中间节点（拆分链表，左边多，右边少）

        ListNode head1 = head;
        ListNode head2 = slow.next;


        //2.将第二个链表逆序
        ListNode tmpHead = new ListNode();
        tmpHead.next = head2;
        ListNode cur = head2.next;
        //ListNode next = null;
        //ListNode nnext = null;
        ListNode first = head2;
        while (cur != null) {//避免出现空指针异常
            tmpHead.next = cur;
            tmpHead.next.next = first;
            first = cur;
            cur = cur.next;
        }


        //3.链表的重新组合
        ListNode retHead = head1;
        while (head2 != null) {
            retHead.next = head2;
            retHead = retHead.next;
            head2 = head2.next;
            head1 = head1.next;
            retHead.next = head1;
            retHead = retHead.next;

        }
        if(head1!=null){
            head1 = head1.next;
            retHead.next = head1;
        }


    }
}